package leetcode.method.dynamic_programming;

import common.bean.TreeNode;

import java.util.*;

/**
 * map记录状态值
 */
public class Program337RobTheHouse {

    public Program337RobTheHouse() {

    }
    public int rob(TreeNode root) {
//        return Math.max(dfs(root,true), dfs(root, false));

//        Map<TreeNode, Integer> select = new HashMap<>();
//        Map<TreeNode, Integer> noSelect = new HashMap<>();
//        dfs(root, select, noSelect);
//        return Math.max(select.getOrDefault(root, 0), noSelect.getOrDefault(root, 0));

        int[] rootStatus = dfs(root);
        return Math.max(rootStatus[0], rootStatus[1]);
    }

    public int dfs(TreeNode root, boolean select) {
        if (root == null) {
            return 0;
        }

        return !select ? Math.max(dfs(root.left, true), dfs(root.left, false))
                + Math.max(dfs(root.right, true), dfs(root.right, false))
                : Math.max(dfs(root.left, true) + dfs(root.right, true),
                root.val + dfs(root.left, false) + dfs(root.right, false));
    }

    public void dfs(TreeNode root, Map<TreeNode, Integer> select, Map<TreeNode, Integer> noSelect) {
        if (root == null) {
            return;
        }
        dfs(root.left, select, noSelect);
        dfs(root.right, select, noSelect);

        select.put(root, root.val + noSelect.getOrDefault(root.left, 0) + noSelect.getOrDefault(root.right, 0));
        noSelect.put(root, Math.max(select.getOrDefault(root.left, 0), noSelect.getOrDefault(root.left, 0)) +
                Math.max(select.getOrDefault(root.right, 0), noSelect.getOrDefault(root.right, 0)));
    }

    private  int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        int selected = root.val + l[1] + r[1];
        int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{selected, notSelected};
    }

    public static void main(String[] args) {

    }
}
